package leetcode;


import java.util.PriorityQueue;

public class l0023_合并K个升序链表_4_优先级队列_小顶堆_推荐采用这种 {

    public ListNode mergeKLists(ListNode[] lists) {
        //前置校验
        if (lists == null || lists.length == 0) {
            return null;
        }
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((ListNode listNode1,ListNode listNode2)->{
            return listNode1.val-listNode2.val;
        });
        //将K个链表的头结点放入堆中
        for (ListNode list : lists) {
            if (list==null){
                continue;
            }
            minHeap.offer(list);
        }
        //不断 删除堆顶元素，并且把堆顶元素的next添加到堆中
        while (!minHeap.isEmpty()){
            ListNode poll = minHeap.poll();
            if (poll.next!=null){
                minHeap.offer(poll.next);
            }
            cur.next=poll;
            cur=cur.next;
        }
        return dummyHead.next;
    }

}
